/**
 * @author 徐楠
 * @date 2022/1/14 16:55
 * @version 1.0
 */

package com.xunan.likou;

import java.util.ArrayList;
import java.util.List;

public class FullPermutationWithoutDuplicateElementSet {

    static List<List<Integer>> result = new ArrayList<>();

    public static void main(String[] args) {

        //int[] nums = {1, 2, 3};
        //int[] nums = {0, 1};
        //int[] nums = {5,4,6,2};
        int[] nums = {5};
        permute(nums);
        System.out.println(result);
    }

    public static List<List<Integer>> permute(int[] nums) {

        /*if (nums.length == 2) {
            List<Integer> list1 = new ArrayList<>();
            list1.add(nums[0]);
            list1.add(nums[1]);
            result.add(list1);
            List<Integer> list2 = new ArrayList<>();
            list2.add(nums[1]);
            list2.add(nums[0]);
            result.add(list2);
            return result;
        }
        if (nums.length == 1) {
            List<Integer> list1 = new ArrayList<>();
            list1.add(nums[0]);
            result.add(list1);
            return result;
        }*/

        Perm(nums, 0, nums.length-1);
        return result;


    }

    public static void Perm(int list[], int k, int m) {
        //list 数组存放排列的数，K表示层 代表第几个数，m表示数组的长度
        if (k == m) {
            List<Integer> list1 = new ArrayList<>();
            //K==m 表示到达最后一个数，不能再交换，最终的排列的数需要输出；
            for (int i = 0; i <= m; i++) {
                list1.add(list[i]);
                //cout<<list[i];
                /*System.out.println("--");
                System.out.println(list[i]);
                System.out.println("--");*/
            }
            result.add(list1);

        } else {
            for (int i = k; i <= m; i++) {
                swap(list, i, k);
                Perm(list, k + 1, m);
                swap(list, i, k);
            }
        }

    }

    public static void swap(int list[], int a, int b) {
        int temp;
        temp = list[a];
        list[a] = list[b];
        list[b] = temp;
    }


    /**
     * 回溯
     *     List<List<Integer>> res = new ArrayList<>();
     *
     *     List<Integer> list = new ArrayList<>();
     *
     *     int[] nums = null;
     *
     *     boolean[] visited = null;
     *
     *     public List<List<Integer>> permute(int[] nums) {
     *         this.nums = nums;
     *         this.visited = new boolean[nums.length];
     *         dfs();
     *         return res;
     *     }
     *
     *     public void dfs(){
     *         if(list.size() == nums.length){
     *             res.add(list);
     *             list = new ArrayList<>(list); // 每添加1个叶子节点必要重新new一个list
     *             return;
     *         }
     *         for(int i = 0;i < nums.length;i ++){
     *             if(visited[i] == true) continue; // 遇到重复的元素就跳过
     *             list.add(nums[i]); // 每次添加1个元素
     *             visited[i] = true;
     *             dfs();
     *             list.remove(list.size()-1);// 撤销选择
     *             visited[i] = false;
     *         }
     *     }
     * */

}
